#include <stdio.h>
#include <stdlib.h>

typedef char ElemType_Tree;
// 二叉树结点
typedef struct BiTNode {
    ElemType_Tree data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode, *BiTree;
// 层序建树辅助队列结点
typedef struct QueueNode {
    BiTNode *p;
    struct QueueNode *next;
}QueueNode, *TagQueue;

// 前序遍历二叉树
void preOrder(BiTree T) {
    if (T != NULL) {
        printf("%c", T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

/**
 * 读取字符串abcdefghij，然后层次建树建立一颗二叉树，然后前序遍历输出abdhiejcfg
 * @return
 */
int main() {

    // 二叉树
    BiTree tree = NULL;
    // 辅助队列
    QueueNode *queueHead = NULL, *queueTail = NULL;   // 指向辅助队列的头和尾
    QueueNode *pcur;    // 记录当前插入结点在辅助队列中的位置

    // 接收数据
    ElemType_Tree e;
    while (scanf("%c", &e) != EOF) {
        if (e == '\n') {
            break;
        }
        // 生成树结点
        BiTNode *pnew = (BiTNode*) calloc(1, sizeof (BiTNode)); // calloc()申请空间并对空间进行初始化，赋值为0
        pnew->data = e;
        // 生成辅助队列结点
        QueueNode *queueNew = (QueueNode*) calloc(1, sizeof (QueueNode));
        queueNew->p = pnew;

        // 加入辅助队列和树
        if (tree == NULL) {
            // 初始化队列（插入第一个结点）
            queueHead = queueNew;
            queueTail = queueNew;
            // 初始化树（插入第一个结点）
            tree = pnew;
            pcur = queueNew;
        } else {
            // 插入辅助队列
            queueTail->next = queueNew;
            queueTail = queueNew;
            // 插入树。如果结点左子树为空，则插入左子树；否则插入右子树，并将辅助队列当前结点后移一位
            if (pcur->p->lchild == NULL) {
                pcur->p->lchild = pnew;
            } else {
                pcur->p->rchild = pnew;
                pcur = pcur->next;
            }
        }
    }

    // 前序遍历二叉树
    preOrder(tree);

    return 0;
}